`
https://leetcode.cn/problems/3sum-with-multiplicity/
`

/**
 * @param {number[]} arr
 * @param {number} target
 * @return {number}
 */
var threeSumMulti = function (arr, target) {
  const MOD = 1e9 + 7
  const mx = Math.max(...arr)
  const cnt = new Array(mx + 1).fill(0)
  for (const num of arr) {
    cnt[num]++
  }
  let res = 0

  // 枚举 i
  for (let i = 0; i < mx + 1; i++) {
    // 不存在这个数
    if (cnt[i] === 0) continue
    // 加不到 target
    if (i + 2 * mx < target) continue
    // 自己加三次就超过 target，不可能再找到
    if (i * 3 > target) break
    let left = i, right = mx
    while (left <= right) {
      const s = i + left + right
      if (s > target) {
        right--
      } else if (s < target) {
        left++
      } else {
        // 找到结果
        if (left === right && right === i) {
          // 三个数都相等
          // 组合数 C(n, 3) = n * (n - 1) * (n - 2) / 6
          res += (cnt[i] * (cnt[i] - 1) * (cnt[i] - 2) / 6) % MOD
        } else if (left === right) {
          // 两个数相等
          res += (cnt[left] * (cnt[left] - 1) / 2 * cnt[i]) % MOD
        } else if (left === i) {
          res += (cnt[i] * (cnt[i] - 1) / 2 * cnt[right]) % MOD
        } else {
          // 一般情况
          res += (cnt[i] * cnt[left] * cnt[right]) % MOD
        }
        left++
        right--
      }
    }
  }

  return res % MOD
};